home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 September / macformat-028.iso / mac / Shareware City / Science / GA-and-CA / Eck's Genetic Algorithm Program / ABOUT "GA" next >
Encoding:
Text File  |  1995-06-13  |  8.8 KB  |  165 lines  |  [TEXT/R*ch]
  1.  
  2.                                                          June 13, 1995
  3.  
  4. David Eck
  5. Department of Mathematics and Computer Science
  6. Hobart and William Smith Colleges
  7. Geneva, NY 14456   USA
  8. E-mail:  eck@hws.edu
  9. WWW:     http://hws3.hws.edu:9000/eck/index.html
  10.          (Also, visit http://math.hws.edu/TMCM.html for information
  11.           on my new introductory computer science textbook.)
  12.  
  13.  
  14. COPYRIGHT RESTRICTIONS:  The program GA can be freely distributed
  15. for private, non-commercial use.  It can be included on inexpensive
  16. CD-ROM shareware collections.  It can be made available for
  17. downloading from FTP sites and on-line services, provided that no
  18. charge is made beyond such basic charges as connect time and
  19. membership fee.
  20.  
  21.  
  22. ABOUT THE PROGRAM:
  23. -----------------
  24.  
  25.      "GA" is a little program that demonstrates the genetic algorithm,
  26. in which methods analogous to the process of natural evolution are
  27. applied to solve problems on a computer.  This "artificial evolution"
  28. uses reproduction, mutation, and genetic recombination to "evolve" a
  29. solution to a problem.  The genetic algorithm is described fully by
  30. John Holland in his book, "Adaptation in Natural and Artificial
  31. Systems."  More popular accounts can be found in the books "Complexity"
  32. by M. Mitchell Waldrop and "Artificial Life" by Steven Levy.
  33.  
  34.      The genetic algorithm can be applied to many different types of
  35. problems, but GA uses it to evolve simulated "organisms" called Eaters
  36. in a simulated world that contains simulated plants for the Eaters to
  37. eat.  I stress the word "simulated", but even that word really goes too
  38. far.  GA is really just a kind of metaphore for natural evolution in 
  39. the real world.  You can judge for yourself the extent to which that
  40. metaphore might be valid.
  41.  
  42.      When you first start up the program, you will see a world containing
  43. 250 plants and 25 Eaters.  The plants tend to grow in clumps.  The Eaters
  44. will display random-looking, undirected behavior, but sometimes an Eater
  45. will eat a plant.  (It does this merely my moving to the postion occupied
  46. by the plant.)  At the end of each year, a new world is produced,
  47. containing a new generation of Eaters.  The new Eaters are produced as
  48. copies, with modification, of Eaters from the previous generation.
  49. The more plants that an Eater has eaten, the better its chances of
  50. producing "offspring" in the new generation.  Differential reproduction,
  51. based on "fitness" defined as the number of plants eaten, would by itself
  52. tend to increase the average fitness of the population.  The random
  53. modifications introduced during reproduction allow new behaviors to
  54. be tested and, if they turn out to be advantageous, to spread through
  55. the population in later generations.  There are two types of modification:
  56. "mutation", in which random changes are introduced as an Eater is copied,
  57. and "crossover", in which a new Eater is made by combining parts of
  58. the genetic makup of two Eaters from the previous generation.
  59.  
  60.      This is all you really need to know to start playing with the
  61. program.  The rest of this file contains the details you need in order
  62. to understand what is going on.
  63.  
  64.      The Eaters' world is divided into little squares.  Each square can
  65. hold an Eater or a plant, or it can be blank.  A square cannot be occupied
  66. by two things at once.  An Eater can "see" the single square just in
  67. front of it.  (The front is the pointy end of the T-shaped Eater.)  It
  68. can see one of four different things: an Eater, a plant, a blank space,
  69. or a wall.  In addition to this external information, the Eater has
  70. an internal memory that contains a number between 0 and 15.  This number
  71. is called the "state" of the Eater.  At each time step, the Eater can
  72. perform one of the actions:
  73.               1. Move forward one square
  74.               2. Move backwards one square
  75.               3. Turn in place 90 degrees to the left
  76.               4. Turn in place 90 degrees to the right.
  77. It can also change its state by changing the number in its memory.
  78. If it tries to move into a wall or onto a square that already contains
  79. another Eater, it will not be allowed to move; however, it can still
  80. change its state.  If it moves onto a square containing a plant, it
  81. "eats" the plant and scores a point.  Depending on menu settings, the
  82. plant might immediately grow back somewhere else.  At the end of a year,
  83. the "fitness" of the Eater is the number of plants it has eaten PLUS ONE.
  84. (The 1 is added to avoid having a fitness of zero.)
  85.  
  86.     Now, how does an Eater decide what to do on each turn?  It bases
  87. its decision on two things, its current state and the item that it
  88. sees in front of it.  Its behavior is completely determined by
  89. a set of rules that tell it what to do for each possible combination 
  90. of current state and item-in-view.  All the Eater does is follow its
  91. rules.  The rules differ from one Eater to another.  In fact, the Eater's 
  92. rules, which completely determine the behavior of the Eater, make up
  93. the Eater's genetic endowment, what we will call its "chromosome".  
  94. The chromosome consists of 64 rules (one for each combination of one
  95. of 16 states and one of four items-in-view).  Each rule specifies
  96. two things: an action and a new state.  The chromosome can be considered
  97. to be just a list of 128 numbers.
  98.  
  99.     Here is what happens at the end of a year:  The average fitness of
  100. the current population is computed.  A new population is created by
  101. making copies of the Eaters (that is, of the chromosomes) in the
  102. current population.  An Eater's chance of being copied depends on its
  103. fitness.  Eaters that have fitness much below average are likely not
  104. to be reproduced at all (although they always have some chance of 
  105. reproduction.)  Eaters with high fitness are likely to be copied several
  106. times.  Then a mutation operation is applied:  Each of the 128 numbers
  107. in each chromosome has a chance of being randomly changed.  This chance
  108. is 1% by default and is controlled by the Mutation Probability submenu
  109. of the World Design menu.  (Note that a 1% mutation probabilty is
  110. already quite high, since every chromosome is likely to have at least
  111. one of its rules modified.)  Finally, a crossover operation is perfromed:
  112. Pairs of Eaters in the new population are chosen at random and have
  113. a certain probability of being "crossed over".  This probability is
  114. 75% by default and is controlled by the Crossover Probability submenu
  115. of the World Design menu.  Crossover here means that the chromosomes
  116. exchange some genetic material; a random position between 1 and 128 is
  117. chosen and all data on the chromosomes after that position are swapped
  118. between the two chromosomes.
  119.  
  120.     The new Eaters are placed in a new world with a new set of plants.
  121. They are initially in state number zero and are facing in random
  122. directions.
  123.  
  124.     The average fitness and the highest individual fitness for the previous
  125. year are displayed at the bottom of the "World" window.  This information
  126. is also--sometimes--added to a "Summany Statistics" window.  (Information
  127. is displayed in this window every year for the first 20 years, then
  128. every tenth year up to the 200-th year, and every 100-th year after
  129. that.  Also, if a new high average score is achieved in a given year,
  130. data for that year is added to the Summary Statistics window.  New
  131. high average scores are starred in this window.)  This window also
  132. shows the "average average score" over the previous hundred years;
  133. for the first hundred years, the number shown is the average of all
  134. the average scores in the current and previous years.  The contents
  135. of this window can be printed using the Print Statistics command in the
  136. File menu.
  137.  
  138.      Various aspects of the world are controlled using the various
  139. submenus of the World Design menu.  Mutation Probability and Crossover
  140. Probability were mentioned above.  Most of the other items in this
  141. menu are either self-explanatory or best left to discovery through
  142. exploration.  Whenever you make a change in this menu, it becomes
  143. operative at first opportunity.  For example, if you change the
  144. setting of the "Plants Grow" submenu, it will have an immediate effect
  145. on the location where plants grow back after begin eaten.  The
  146. Approximate population submenu, on the other hand, will come into 
  147. effect at the end of the current year.
  148.  
  149.      The "Start from Scratch" command in the Control menu will start
  150. over with a new, randomly generated population of Eaters.  (This does
  151. NOT change any of the settings in the World Design menu back to their
  152. default values.)
  153.  
  154.      The five speed settings at the bottom of the Control menu should
  155. be fairly obvious.  Note that speed number 1 is designed to make the
  156. years go by as quickly as possible.  A good technique is to let the
  157. program run in speed 1 until it looks from the average scores like
  158. something interesting has happened.  You can then switch back to speed
  159. 2 or 3 and try to see what new behavior the Eaters have "learned".
  160.  
  161.      The GA program will continue to run in the background, which makes
  162. it easy to investigate what happens over the very long term.
  163.  
  164.  
  165.